package com.llb666.java.leetcode.tree;




import javafx.util.Pair;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * Created by 斌~    堆栈的方式实现
 * 2021/5/18 17:44
 *                         1
 *                  2             3
 *              4      5
 *                 6       7
 */
public class 二叉树遍历2 {
    public static void main(String[] args) {
        TreeNode node7 = new TreeNode(7, null, null);
        TreeNode node6 = new TreeNode(6, null, null);
        TreeNode node5 = new TreeNode(5, node6, node7);
        TreeNode node4 = new TreeNode(4, null, null);
        TreeNode node3 = new TreeNode(3, null, null);
        TreeNode node2 = new TreeNode(2, node4, node5);
        TreeNode node1 = new TreeNode(1, node2, node3);

        List<Integer> perOrderList = perOrder(node1);//前序遍历-递归 1 2 4 5 6 7 3
        List<Integer> midOrderList = midOrder(node1);  //中序遍历-递归 4 2 6 5 7 1 3
        List<Integer> nextOrderList = nextOrder(node1); //后序遍历-递归 4 6 7 5 2 3 1

        nextOrderList.forEach(System.out::println);
    }


    /**
     * ----------------------前序遍历-------------栈实现，根左右
     * 没有访问任何孩子就弹出，接着压入左孩子，右孩子
     * @param root 根节点
     */
    private static List<Integer> perOrder(TreeNode root) {
        Stack<TreeNode> s = new Stack<>();
        List<Integer> ans  = new ArrayList<>();
        for(s.push(root);!s.isEmpty();){
            root = s.pop();
            if(root != null){
                ans.add(root.val);
                s.push(root.right);
                s.push(root.left);
            }
        }
        return ans;
    }


    /**
     * ----------------------中序遍历-------------栈实现，左根右
     * 栈顶访问过左孩子则出栈，记录，押入右孩子
     * 栈顶没有访问孩子，则押入左孩子
     * @param root 根节点
     */
    private static List<Integer> midOrder(TreeNode root) {
        Stack<Pair<TreeNode,Integer>>s = new Stack<>();
        List<Integer> ans  = new ArrayList<>();
        for(s.push(new Pair<TreeNode,Integer>(root,0)); !s.isEmpty();){
            Pair<TreeNode,Integer> temp = s.pop();
            root = temp.getKey();
            if(root != null){
                switch (temp.getValue()){
                    case 0: //栈顶没有访问孩子，则押入左孩子
                        s.push(new Pair<>(root,1));
                        s.push(new Pair<>(root.left,0));
                        break;
                    default: //栈顶访问过左孩子则出栈，记录，押入右孩子
                        ans.add(root.val);
                        s.push(new Pair<>(root.right,0));
                        break;
                }
            }
        }
        return  ans;
    }

    /**
     * ----------------------后序遍历-------------栈实现，左右根
     * 栈顶元素访问过左孩子，压入右孩子
     * 栈顶没有访问过孩子，压入左孩子
     * 栈顶元素访问过左右孩子，则弹出\记录
     * @param root 根节点
     */
    private static List<Integer> nextOrder(TreeNode root) {
        Stack<Pair<TreeNode,Integer>>s = new Stack<>();
        List<Integer> ans  = new ArrayList<>();
        for(s.push(new Pair<TreeNode,Integer>(root,0)); !s.isEmpty();){
            Pair<TreeNode,Integer> temp = s.pop();
            root = temp.getKey();
            if(root != null){
                switch (temp.getValue()){
                    case 0: //栈顶没有访问过孩子，压入左孩子
                        s.push(new Pair<>(root,1));
                        s.push(new Pair<>(root.left,0));
                        break;
                    case 1: // 栈顶元素访问过左孩子，压入右孩子
                        s.push(new Pair<>(root,2));
                        s.push(new Pair<>(root.right,0));
                        break;
                    default:
                        ans.add(root.val);
                        break;
                }
            }
        }
        return  ans;
    }

/**
 *  -----------------------二叉树实体类---------------------------
 */
    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        int deep;

        public TreeNode() {
        }

        public TreeNode(int val) {
            this.val = val;
        }

        private TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}


